from collections import defaultdict
from typing import List, Any


class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1
        edges = defaultdict(list)
        for u, v in roads:
            edges[u].append(v)
            edges[v].append(u)

        def dfs(node: int, fa: int) -> tuple[int | Any, int | Any, int | Any]:
            """
            :param node:
            :param fa:
            :return: 此树全部到达节点node的花费大小, 人数,车数
            """
            cost = 0
            cnts = 1
            cars = 0
            for next_ in edges[node]:
                if next_ == fa: continue
                cos, cnt, car = dfs(next_, node)
                cost += cos
                cnts += cnt
                cars += car
            # 一段路程
            cost += cars
            # 少添多弃
            while cars * seats < cnts: cars += 1
            while (cars - 1) * seats > cnts: cars -= 1
            return cost, cnts, cars

        r = dfs(0, -1)
        return r[0]


if __name__ == '__main__':
    s = Solution()
    r = s.minimumFuelCost(roads=[[0, 1], [0, 2], [1, 3], [1, 4]], seats=5)
    print(r)
